package com.example.demo.lc;

import java.util.Deque;
import java.util.LinkedList;

/**
* @author wzh
* @date 2021/7/23 2:19 下午
* @Description    单调栈
 * https://leetcode-cn.com/problems/trapping-rain-water/
*/
public class LeetCode42 {
    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height));
    }

    public static int trap(int[] height) {
        Deque<Integer> deque = new LinkedList<>();
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            while (!deque.isEmpty() && height[i] > height[deque.peek()]){
                Integer top = deque.pop();
                if(deque.isEmpty())break;
                Integer left = deque.peek();
                int width = i- left -1;
                int h = Math.min(height[i],height[left])-height[top];
                ans += width* h;
            }
            deque.push(i);
        }
        return ans;
    }

}
